#include <iostream>
#include <vector>

using std::endl;
using std::cout;
using std::vector;

struct Node {
  int data;
  Node *next;
};

// Shift the given link list as follows:
// original: head->(head+1)->...->(mid-1)->mid->(mid+1)->...->(end-1)->end
// after shifted: mid->(mid+1)->...->(end-1)->head->(head+1)->...->(mid-1)->end
void ShiftLinkedList(Node *head, Node *mid, Node *end) {
  while (head != mid && mid != end) {  // Both parts are not empty.
    Node *p = head, *q = mid;
    while (p != mid && q != end) {
      std::swap(p->data, q->data);
      p = p->next;
      q = q->next;
    }
    if (p == mid) {
      if (q == end) return;
      // Now the link list looks like:
      // mid->...->(mid+mid-head-1)->head->...->(mid-1)->
      // (mid+mid-head)->...->end
      // The following two lines are equivalent to ShiftLinkedList(mid, q, end).
      head = mid;
      mid = q;
    } else {
      // p != mid, so that it must have q == end, the link list looks like:
      // mid->...->(end-1)->(head+end-mid)->...->(mid-1)->head->...->
      // (head+end-mid-1)->end
      head = p;  // Equivalent to ShiftLinkedList(p, mid, end);
    }
  }
}

void RevertLinkedListWithConstantSpace(Node *head) {
  if (head == NULL) return;
  for (int step = 1; true; step <<= 1) {
    for (Node *begin = head, *mid = NULL, *end = NULL;
         begin != NULL; begin = end) {
      mid = end = begin;
      for (int i = 0; i < step && mid != NULL; ++i) {
        mid = mid->next;
        if (end != NULL && end->next != NULL) {
          end = end->next->next;
        } else {
          end = NULL;
        }
      }
      if (begin == head && mid == NULL) return;
      ShiftLinkedList(begin, mid, end);
    }
  }
}

void RecursivelyRevert(Node *begin, Node *end) {
  if (begin == end) return;
  Node *first_end = begin, *second_end = begin;
  while (second_end != end && second_end->next != end) {
    first_end = first_end->next;
    second_end = second_end->next->next;
  }

  Node *mid = NULL;
  if (second_end == end) {  // Even nodes.
    mid = first_end;
  } else {  // Odd nodes, must be in the case that second_end->next == end.
    mid = first_end->next;
  }
  for (Node *p = begin, *q = mid; p != first_end; ) {
    std::swap(p->data, q->data);
    p = p->next;
    q = q->next;
  }
//  cout << "--";
//  for (Node *o = begin; o != end; o = o->next) {
//    cout << o->data << ", ";
//  }
//  cout << endl;

  RecursivelyRevert(begin, first_end);
  RecursivelyRevert(mid, end);
}

void RevertLinkedListWithLogSpace(Node *head) {
  RecursivelyRevert(head, NULL);
}

void RevertLinkedList_Test(Node *head) {
  vector<int> data;
  for (Node *p = head; p != NULL; p = p->next) {
    data.push_back(p->data);
  }
  for (vector<int>::const_iterator it = data.begin();
       it != data.end(); ++it) {
    cout << *it << ", ";
  }
  cout << endl;

  cout << "Testing non-recursive version..." << endl;
  for (int i = 0; i < 2; ++i) {
    RevertLinkedListWithConstantSpace(head);
    for (Node *p = head; p != NULL; p = p->next) {
      cout << p->data << ", ";
    }
    cout << endl;
  }

  cout << "Testing recursive version..." << endl;
  for (int i = 0; i < 2; ++i) {
    RevertLinkedListWithLogSpace(head);
    for (Node *p = head; p != NULL; p = p->next) {
      cout << p->data << ", ";
    }
    cout << endl;
  }
}

int main() {
  const int kMaxSize = 1024;
  Node node[kMaxSize];
  for (int i = 0; i < kMaxSize - 1; ++i) {
    node[i].data = i;
    node[i].next = &(node[i + 1]);
  }

  cout << "Size: " << 5 << endl;
  node[4].next = NULL;
  RevertLinkedList_Test(node);

  cout << "Size: " << 6 << endl;
  node[4].next = &(node[5]);
  node[5].next = NULL;
  RevertLinkedList_Test(node);
  return 0;
}
